def quick_pow(a,b,p):
    assert a>0 and b>0 and p>0
    ans = 1 % p 
    while(b):
        if(b & 1):
            ans=(ans*a)%p 
        a = (a*a)%p
        b>>=1
    return ans 